package 寒假刷题;

import java.util.Arrays;
import java.util.List;

public class 三角形最短路径和 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        //表示到达第i行第j列的最小路径
        int[][] dp = new int[n][n+1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i],Integer.MAX_VALUE);
        }
        //初始化，第一行第一列的值是固定的
        for (int i = 1; i <= triangle.get(0).size(); i++) {
            dp[0][i] = triangle.get(0).get(i - 1);
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= triangle.get(i).size(); j++) {
                //dp[i][j]只能由上一行的dp[i-1][j]或dp[i-1][j-1]得到
                dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1])+triangle.get(i).get(j-1);
            }
        }
        //返回最后一行的最小值
        return Arrays.stream(dp[n-1]).min().getAsInt();
    }
    public int minimumTotal1(List<List<Integer>> triangle) {
        if (triangle.size()==0 || triangle==null)
            return 0;
        int n = triangle.size();
        int[][] dp = new int[n + 1][n + 1];
        //自底向上遍历
        for (int i = n-1;i>=0;i--){
            List<Integer> list = triangle.get(i);
            for (int j = 0; j < list.size(); j++) {
                dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1])+list.get(j);
            }
        }
        return dp[0][0];
    }
}
